class test_12_2_1 {

    static class ListNode {
        public int val;//存储的数据
        public ListNode next;//存储下一个节点的地址
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;// 代表当前链表的头节点的引用

    public void createLink() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        head = listNode1;
    }



    public ListNode reverseList() {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }



    public ListNode middleNode() {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }



    public ListNode findKthToTail(int k) {
        if (k <= 0 || head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (k - 1 != 0) {
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            k--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }



    public boolean chkPalindrome() {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        //1、找中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2、 翻转
        ListNode cur = slow.next;//代表当前需要翻转的节点
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3、一个从头往后  一个从后往前
        while (slow != head) {
            if (head.val != slow.val) {
                return false;
            }
            //偶数的情况
            if (head.next == slow) {
                return true;
            }
            slow = slow.next;
            head = head.next;

        }
        return true;
    }


}




